/*
 * 快排是经常被面试官问到的基本算法，仔细研究一下发现它
 * 并不神秘，它是冒泡算法的改进，都属于交换排序。但是快排
 * 的效率要高出很多，因为它并不像冒泡排序那样只比较相邻的
 * 位置，而是大范围的比较，尽快把大小数据给划分开；这样就
 * 会减少了比较的次数，从而提高了效率。
 *
 * 最好时间复杂度：O(nlog2 n)
 * 平均时间复杂度：O(nlog2 n)
 * 最坏时间复杂度：O(n^2)
 *
 * 快速排序是经常用到的高效率的算法，适合数据比较离散的
 * 情况，著名的应用应该非qsort()莫属了
 */

#include <stdio.h>

void quicksort(int a[], int l, int r);
static int partition(int a[], int i, int j);
static inline void swap(int *a, int *b);

int main()
{
	int a[10] = {10, 8, 7, 3, 2, 20, 9, 1, 100, 23};

	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");

	quicksort(a, 0, 9);

	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

void quicksort(int a[], int l, int r)
{
	int m;

	if (l < r) {
		m = partition(a, l, r);
		quicksort(a, l, m - 1);
		quicksort(a, m + 1, r);
	}
}

static int partition(int a[], int i, int j)
{
	while (i < j) {
		while (i < j && a[i] <= a[j]) j--;
		if (i < j) {
			swap(&a[i], &a[j]);
			i++;
		}

		while (i < j && a[i] <= a[j]) i++;
		if (i < j) {
			swap(&a[i], &a[j]);
			j--;
		}
	}

	return i;
}

static inline void swap(int *a, int *b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}
